package problem.year2021.february;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
 * <p>
 * 在杨辉三角中，每个数是它左上方和右上方的数的和。
 * <p>
 * 示例:
 * <p>
 * 输入: 3
 * 输出: [1,3,3,1]
 * <p>
 * 进阶：
 * <p>
 * 你可以优化你的算法到 O(k) 空间复杂度吗？
 */
public class February12 {
    // 未经过优化的计算
    public List<Integer> getRow(int rowIndex) {
        if (rowIndex < 3) {
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < rowIndex; ++i) {
                list.add(1);
            }
            return list;
        }
        // 元素总数目
        int sum = (int) ((rowIndex + 1) / 2.0 * rowIndex);
        // 根据杨辉三角的特性，第K行有K个元素;而其总共元素有（k+1）/2*k
        int[] numbers = new int[sum];
        for (int i = 1; i <= rowIndex; ++i) {
            for (int j = 1; j <= i; ++j) {
                if (j == 1 || j % i == 0) {
                    int index = (int) ((rowIndex + 1) / 2.0 * rowIndex) + j;
                    numbers[index] = 1;
                    continue;
                }
                int index = (int) ((rowIndex + 1) / 2.0 * rowIndex) + j;
                int index1 = index - (i - 1);
                int index2 = index1 + 1;
                numbers[index] = numbers[index1] + numbers[index2];
            }
        }
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < rowIndex; ++i) {
            list.add(numbers[sum - i - 1]);
        }
        return list;
    }
    // 经过优化的计算

    public static void main(String[] args) {
        int rowIndex = 4;
        int sum = (int) ((rowIndex + 1) / 2.0 * rowIndex);
        System.out.println(sum);
    }
}
